package GreedyAlgorithm;

import java.util.PriorityQueue;

/**
 * @author Liaorun
 */
public class LessMoneySplitGold {
    public static int lessMoney(int[] arr) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        // 所有需要分的金子的大小放到小根堆
        for (int i : arr) {
            priorityQueue.add(i);
        }

        // 分金子需要的代价
        int sum = 0;
        int cur;

        while (priorityQueue.size() > 1) {
            // 每次弹出两个相加
            cur = priorityQueue.poll() + priorityQueue.poll();
            // 加上此次分金子需要的代价
            sum += cur;
            priorityQueue.add(cur);
        }

        return sum;
    }
}
